1516. Создание двоичного дерева поиска
БДП (бинарное
дерево поиска) является эффективной структурой для поиска. В БДП все элементы
левого поддерева меньше, а все элементы правого поддерева больше чем значение
корня. Рассмотрим пример БДП:
Обычно БДП строится
в результате последовательной вставки элементов. В таком случае
последовательность вставки элементов влияет на структуру результирующего
дерева. Например:
В этой задаче Вам необходимо найти такой
порядок вставки чисел от 1 до n,
чтобы полученное БДП имело высоту не больше h.
Высота БДП определяется следующим образом:
1. Высота БДП,
которое не содержит ни одной вершины, равна 0.
2. Иначе высота
БДП равна 1 плюс максимум высот левого и правого поддерева.
Условию задачи
могут удовлетворять несколько последовательностей вставок. В таком случае
следует вывести последовательность, в которой сначала идут меньшие числа.
Например, для n = 4, h = 3 следует вывести последоватлеьность
1 3 2 4, а не 2 1 4 3 или 3 2 1 4.
Вход. Каждый тест содержит два натуральных числа n (1 ≤ n ≤ 10000) и h (1
≤ h ≤ 30). Последний тест
содержит n = 0, h = 0 и не обрабатывается. На вход подается не более 30 тестов.
Выход. Результат каждого теста следует вывести в
отдельной строке. Каждая строка начинается с "Case #: ", где "#"
– номер теста. Дальше в этой же строке следует вывести последовательность из n целых чисел – порядок вершин, в
котором они будут вставляться в БДП высоты не более h. В конце строки не должно быть пробелов. Если требуемое дерево
построить нельзя, то вывести "Impossible." (без кавычек).
|
Пример
входа |
Пример
выхода |
|
4 3 4 1 6 3 0 0 |
Case 1: 1 3
2 4 Case 2:
Impossible. Case 3: 3 1
2 5 4 6 |
РЕШЕНИЕ
рекурсия
Анализ алгоритма
Полное бинарное дерево высоты h содержит 1 + 2 + 4 + … + 2h-1
= 2h – 1 вершин. Если n ³ 2h,
то искомого дерева не существует. Иначе будем строить такое дерево, в котором
будет по максимуму заполняться правое поддерево.
Пусть следует
расположить в дереве поиска высоты не более h
числа от a до b. Тогда в правом поддереве высоты h – 1 следует расположить 2h-1
– 1 элементов, а число d = b – 2h-1
+ 1 следует расположить в корне. Числа от a
до d – 1 располагаем в левом
поддереве, а числа от d + 1 до b в правом.
Если d < a, то в левом поддереве чисел не будет и в таком случае положим d = a.
Пример
Рассмотрим
второй пример, где n = 6, h = 3. Дерево высоты 3 может содержать
до 23 – 1 = 7 вершин. В корне
дерева расположим число d = 6 – (22
– 1) = 3. Рекурсивно вставляем числа от 1 до 2 в левое поддерево и числа от 4
до 6 в правое. Получим последовательность 3 1 2 5 4 6.
Реализация алгоритма
void find(int
a, int b, int
h)
{
int d = b -
(1 << (h-1)) + 1;
if (a > b)
return;
if (d < a)
d = a;
printf("
%d",d);
find(a,d-1,h-1);
find(d+1,b,h-1);
}
Последовательно
читаем входные значения n и h, печатаем номер теста. Проверяем,
существует ли искомое дерево: выводим ‘Impossible.’, если n ³ 2h.
Иначе выводим искомую последовательность вершин, вызвав функцию find(1, n, h).
while(scanf("%d %d",&n,&h), n+h)
{
printf("Case
%d:",cs++);
if (n >=
1 << h) printf(" Impossible.");
else
find(1,n,h);
printf("\n");
}
Java реализация
import java.util.*;
public class Main
{
static void find(int a, int b, int h)
{
int d = b - (1 << (h-1)) + 1;
if (a > b) return;
if (d < a) d = a;
System.out.print("
" +
d);
find(a,d-1,h-1);
find(d+1,b,h-1);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt(), h = con.nextInt();
int cs = 1;
while(n + h > 0)
{
System.out.print("Case
" +
cs++ + ":");
if (n >= 1 << h) System.out.print(" Impossible.");
else find(1,n,h);
System.out.println();
n = con.nextInt(); h = con.nextInt();
}
}
}